Mục tiêu 🎯
- Nhiệm vụ: Tìm đường đi tốt nhất từ máy chủ nguồn `S` đến tất cả các máy chủ khác.
- Kết quả đầu ra: Với mỗi máy chủ `i`, bạn phải tính toán:
- Tổng độ trễ: Chi phí tối thiểu (đường đi ngắn nhất) từ `S` đến `i`.
- Hops tiếp theo: Máy chủ *đầu tiên* trên đường đi ngắn nhất đó.
- Ví dụ: Nếu đường đi tốt nhất từ `S` đến `D` là `S -> A -> B -> D`, thì **Hops tiếp theo** là `A`.
Mạng lưới 💾
Chúng ta sẽ sử dụng một Danh sách kề để lưu trữ mạng lưới.
- Các máy chủ là các nút.
- Các kết nối là các cạnh hai chiều.
- Độ trễ là một trọng số dương.
// Kết nối: 0-1 (10ms), 0-2 (3ms)
adj = [
0:[(1, 10), (2, 3)],
1:[(0, 10)],
2:[(0, 3)],
...
]
adj = [
0:[(1, 10), (2, 3)],
1:[(0, 10)],
2:[(0, 3)],
...
]
Định dạng đầu ra ⚙️
Bạn phải in ra `V` dòng. Mỗi dòng `i` tương ứng với máy chủ `i`.
[độ trễ] [hops tiếp theo]Đối với một nút có thể truy cập được.
0 -1Nếu nút đó chính là nguồn `S`.
-1 -1Nếu nút đó không thể truy cập được từ `S`.